// https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247487246&idx=1&sn=4a514020ce9dc8777e2d1d503188b62b&chksm=9bd7f106aca078108102fe76799983ee8ea3bd759508e6dbfe87bc9da6edbeb8b8dd73deb0d7&scene=178&cur_album_id=1318896187793260544#rd

// 假设 1 个左括号需要匹配 2 个右括号才叫做合法的括号组合，那么给你输入一个括号串s，请问你如何计算使得s合法的最小插入次数呢？

/*
给你一个括号字符串 s ，它只包含字符 ‘(’ 和 ‘)’ 。一个括号字符串被称为平衡的当它满足：
任何左括号 ‘(’ 必须对应两个连续的右括号 ‘))’ 。
左括号 ‘(’ 必须在对应的连续两个右括号 ‘))’ 之前。
即： 1 个左括号需要匹配 2 个右括号才叫做合法的括号组合。
*/

class Test
{
    public int minInsertions(String s) {
         char[] arr = s.toCharArray();

        int need_left = 0, need_right = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {
                // )(
                need_right += 2;
            }

            if (arr[i] == ')') {
                need_right--;

                // 说明右括号太多了

                // 当need == -1时，意味着我们遇到一个多余的右括号，显然需要插入一个左括号
                // 比如说当s = ")"，我们肯定需要插入一个左括号让s = "()"，但是由于一个左括号需要两个右括号，所以对右括号的需求量变为 1：

                if (need_right == -1) {
                    // 需要插入一个左括号
                    need_left++;

                    // 同时，对右括号的需求变为 1
                    need_right = 1;
                }
            }
        }

        return need_left + need_right;
    }
}